package com.yan_jiu_sheng.daily.AC;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/double-modular-exponentiation/description/?envType=daily-question&envId=2024-07-30
 * 快速幂  学习通过
 * 参考学习：https://blog.csdn.net/m0_52072919/article/details/116400820
 *
 * @author yulongtian
 * @create 2024-07-30 10:15
 */
public class Test20240730 {
    public static void main(String[] args) {

    }

    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < variables.length; i++) {
            int a = variables[i][0];
            int b = variables[i][1];
            int c = variables[i][2];
            int m = variables[i][3];
            // Math.pow(Math.pow(a, b) % 10, c) % m
            if (quik_power(quik_power(a, b, 10), c, m) == target) {
                res.add(i);
            }
        }
        return res;
    }

    public int quik_power(int base, int power, int mod) {
        int result = 1;
        while (power > 0) {
            if ((power & 1) == 1) {
                result = result * base % mod;
            }
            base = base * base % mod;
            power >>= 1;
        }
        return result % mod;
    }

}
